#ifndef DINIC_H_
#define DINIC_H_

#include <vector>
#include <assert.h>
#include <math.h>

#include <boost/noncopyable.hpp>

#include "graph_support/Graph.h"

#include "graph_support/utils/PtrAccessOpSimulator.h"
#include "graph_support/utils/GraphTemplateUtils.h"

namespace GRAPH_SUPPORT_NS
{
namespace alg
{
namespace flow
{

template< typename GraphT >
class Dinic : private boost::noncopyable
{
private:
	typedef GraphT Graph;
	typedef typename Graph::GrVertex GrVertex;
	typedef typename Graph::GrEdge GrEdge;
	typedef typename Graph::GrEdgePtr GrEdgePtr;
	typedef typename Graph::VertexIterator VertexIterator;
	typedef typename Graph::EdgeIterator EdgeIterator;
	typedef typename Graph::EdgeAttributes EdgeAttributes;
	typedef typename Graph::EdgeAttributes::Capacity Capacity;

public:
	Dinic( Graph & gr )
		: gr( gr )
		, totalFlow( 0 )
	{
	}

	Capacity getTotalFlow()
	{
		return totalFlow;
	}

	Capacity getFlow( const GrVertex & a, const GrVertex & b )
	{
		return utils::getFlow( gr, a, b );
	}

	void operator () ( const GrVertex & srcVert, const GrVertex & destVert )
	{
		using namespace GRAPH_SUPPORT_NS::utils;

		size_t n = gr.getVertexCount();
		for ( int vid = 0; vid < n; vid++ )
		{
			std::for_each( gr.getEdgsBegId( vid ), gr.getEdgsEndId( vid ),
					boost::bind( & EdgeAttributes::eraseFlow, boost::bind( & GrEdge::getAttributes,
							boost::bind( ptr2ref< GrEdge, GrEdgePtr >, _1 ) ) ) );
		}
		totalFlow = 0;

		// TODO 9 [blocked performance] decide if it is better to use vertex id
		std::vector< size_t > queueBuf( n );
		std::vector< GrEdgePtr > edgeFromParentBuf( n );
		std::vector< char > visitedBuf( n );

		while ( bfs( srcVert, destVert, queueBuf, & edgeFromParentBuf[0], & visitedBuf[0] ) )
		{
			pushFlow( srcVert, destVert, & edgeFromParentBuf[0] );
		}
	}

private:
	bool bfs(
			const GrVertex & srcVert,
			const GrVertex & destVert,
			std::vector< size_t > & queueBuf,
			GrEdgePtr * edgeFromParent,
			char * bfsState )
	{
		// TODO 9 [blocked - performance test] use implemented BFS here
		size_t n = gr.getVertexCount();
		if ( n == 0 )
		{
			return false;
		}

		size_t * queueHead = & queueBuf[0];
		size_t * queueTail = queueHead;
		size_t * queueLim = queueHead + queueBuf.size();
		std::fill( queueHead, queueLim, ( size_t ) Graph::NOT_A_VERTEX_ID );
		char BFS_NEW = 0;
		char BFS_QUEUED = 1;
		char BFS_COMPLETED = 2;
		std::fill( bfsState, bfsState + n, BFS_NEW );
		std::fill( edgeFromParent, edgeFromParent + n, ( GrEdgePtr ) NULL );

		* queueTail = gr.vert2num( srcVert );
		bfsState[gr.vert2num( srcVert )] = BFS_QUEUED;
		queueTail++;

		size_t destID = gr.vert2num( destVert );

		while ( queueHead != queueTail )
		{
			size_t vid = * queueHead;
			queueHead++;
			assert( bfsState[vid] == BFS_QUEUED );
			assert( vid != Graph::NOT_A_VERTEX_ID );
			if ( bfsState[destID] )
			{
				break;
			}

			EdgeIterator stopIt = gr.getEdgsEndId( vid );
			for ( EdgeIterator it = gr.getEdgsBegId( vid ); it != stopIt; ++it )
			{
				GrEdgePtr eptr = * it;
				Capacity rcap = eptr->getAttributes().getRemainCapacity();
				size_t endID = eptr->endId();
				if ( rcap > 0 && ! bfsState[endID] )
				{
					assert( queueTail < queueLim );
					* queueTail = endID;
					queueTail++;
					edgeFromParent[endID] = eptr;
					bfsState[endID] = BFS_QUEUED;
				}
			}

			bfsState[vid] = BFS_COMPLETED;
		}

		return bfsState[destID];
	}

	void pushFlow( const GrVertex & srcVert, const GrVertex & destVert, GrEdgePtr * edgeFromParent )
	{
		size_t destVid = gr.vert2num( destVert );
		size_t srcVid = gr.vert2num( srcVert );
		assert( & ( * ( edgeFromParent[destVid] ) ) != NULL );
		assert( srcVid != destVid );

		// TODO 7 [blocked performance] potential performance improvement ( use global )
		std::vector< EdgeAttributes * > dest2srcBackEdges;
		for ( size_t curVid = destVid; curVid != srcVid;
				curVid = edgeFromParent[curVid]->begId() )
		{
			assert( curVid != Graph::NOT_A_VERTEX_ID );
			assert( dest2srcBackEdges.size() < gr.getVertexCount() );
			assert( edgeFromParent[curVid] != NULL );
			dest2srcBackEdges.push_back( & edgeFromParent[curVid]->getAttributes() );
		}
		assert( dest2srcBackEdges.size() > 0 );

		/**
		 * looks sophisticated, see first doc for GRAPH_SUPPORT_NS::Graph for details
		 */
		Capacity minCap = std::accumulate( dest2srcBackEdges.begin(), dest2srcBackEdges.end(), // iter range
			dest2srcBackEdges[0]->getRemainCapacity(), // first min
			boost::bind( & std::min< Capacity >, _1,
				boost::bind( & EdgeAttributes::getRemainCapacity, _2 ) ) ); // iter->getRemainCapacity()
		assert( minCap > ( Capacity ) 0 ); // constructor Capacity( int ) ; const Capacity & operator = ( int )

		std::for_each( dest2srcBackEdges.begin(), dest2srcBackEdges.end(), // iter range
				boost::bind( & EdgeAttributes::addFlow, _1, boost::ref( minCap ) ) ); // iter->getAttributes().addFlow( minCap )
		assert( ( ( Capacity ) EPS ) >= // path was erased
			std::accumulate( dest2srcBackEdges.begin(), dest2srcBackEdges.end(), // iter range
				dest2srcBackEdges[0]->getRemainCapacity(), // first min
				boost::bind( &std::min< Capacity >, _1,
						boost::bind( & EdgeAttributes::getRemainCapacity, _2 ) ) ) );

		totalFlow += minCap;
	}

private:
	static const double EPS = 1e-5;

private:
	Graph & gr;
	Capacity totalFlow;
};

}
}
}

#endif /* DINIC_H_ */
